package uestc.lj.basicPromotion.kmp;

/**
 * @Author:Crazlee
 * @Date:2021/12/1
 */
public class Code02_IsRotation {
	public static boolean isRotation(String a, String b) {
		if (a == null || b == null || a.length() != b.length()) {
			return false;
		}
		String str = b + b;
		return genIndexOf(str, a) != -1;
	}

	private static int genIndexOf(String s, String m) {
		if (s.length() < m.length()) {
			return -1;
		}
		char[] sChars = s.toCharArray();
		char[] mChars = m.toCharArray();
		int si = 0, mi = 0;
		int[] next = getNextArray(mChars);
		while (si < sChars.length && mi < mChars.length) {
			if (sChars[si] == mChars[mi]) {
				si++;
				mi++;
			} else {
				if (next[mi] == -1) {
					si++;
				} else {
					mi = next[mi];
				}
			}
		}
		return mi == mChars.length ? si - mi : -1;
	}

	private static int[] getNextArray(char[] chars) {
		if (chars.length == 1) {
			return new int[]{-1};
		}
		int[] next = new int[chars.length];
		next[0] = -1;
		next[1] = 0;
		int index = 2;
		int cn = 0;
		while (index < next.length) {
			if (chars[index - 1] == chars[cn]) {
				next[index++] = ++cn;
			} else if (cn > 0) {
				cn = next[cn];
			} else {
				next[index++] = 0;
			}
		}
		return next;
	}

	public static void main(String[] args) {
		String str1 = "yunzuocheng";
		String str2 = "zuochengyun";
		System.out.println(isRotation(str1, str2));

	}
}
